package no31;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/15 10:58
 * 栈的压入弹出序列
 * https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
 */
public class Solution {

    // 未优化
    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        // 边界判断
        if (pushed == null || popped == null || pushed.length == 0 || popped.length == 0) {
            return true;
        }
        // 模拟栈的压入弹出序列
        int pushIndex = 0; // 指向压栈序列
        int popIndex = 0; // 指向弹出序列
        int lengthPush = pushed.length;
        int lengthPop = popped.length;
        Deque<Integer> stack = new ArrayDeque<>(); // 创建栈
        while (popIndex < lengthPop) {
            if (stack.isEmpty() || stack.peek() != popped[popIndex]) {
                // 如果当前栈顶元素与出栈序列相应位置不同, 则不断入栈
                if (pushIndex >= lengthPush) {
                    return false; // 如果此时压栈序列已经遍历结束, 说明不存在
                }
                stack.push(pushed[pushIndex++]);
            } else {
                // 如果相同, 则出栈栈顶, 并移动 popIndex 位置, 重复操作
                stack.pop();
                popIndex++;
            }
        }
        // 最终只需要栈是否为空
        return stack.isEmpty();
    }

    // 优化
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int popIndex = 0; // 用于遍历出栈序列
        // 遍历入栈序列, 不断压栈
        for (int num : pushed) {
            stack.push(num);
            // 判断当前栈顶元素是否与出栈序列相匹配, 如果匹配则不断弹出
            while (!stack.isEmpty() && stack.peek() == popped[popIndex]) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}
